{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "线性代数，起源于对线性方程组（system of linear equations）的解（solution）的研究。\n",
    "而矩阵，最初是线性方程组的简便写法。\n",
    "\n",
    "## 一、从线性方程组到矩阵\n",
    "\n",
    "线性方程组\n",
    "\n",
    "$\\begin{cases}\n",
    "    2x&-y&=0\\\\\n",
    "    -x&+2y&=3\n",
    "\\end{cases}$，$(x, y)$ 可看作两条直线的交点。\n",
    "\n",
    "可以把系数写成列向量，简写成下列形式\n",
    "\n",
    "$\\begin{bmatrix}\n",
    "    2\\\\\n",
    "    -1\n",
    "\\end{bmatrix}x+\n",
    "\\begin{bmatrix}\n",
    "    -1\\\\\n",
    "    2\n",
    "\\end{bmatrix}y=\n",
    "\\begin{bmatrix}\n",
    "    0\\\\\n",
    "    3\n",
    "\\end{bmatrix}$\n",
    "\n",
    "显然，上述方程的左边，是两个**列向量的线性组合**。而 $x$ 和 $y$ 就是能使等式成立的组合系数。\n",
    "\n",
    "在定义的矩阵的乘法后，可进一步简写成下列形式\n",
    "\n",
    "$\\begin{bmatrix}\n",
    "    2&-1\\\\\n",
    "    -1&2\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "    x\\\\\n",
    "    y\n",
    "\\end{bmatrix}=\n",
    "\\begin{bmatrix}\n",
    "    0\\\\\n",
    "    3\n",
    "\\end{bmatrix}$\n",
    "\n",
    "抽象为 $Ax=b$，称作矩阵方程。\n",
    "\n",
    "总结一下，就是可以从三个不同的角度来看待一个线性方程组：**矩阵方程、向量方程和线性方程组**。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 二、方程组的解法\n",
    "\n",
    "### 2.1 行简化算法\n",
    "\n",
    "即对矩阵做若干**初等行变换**，将原矩阵变换成**行阶梯形式（row echelon form, rref）**。这一步也被称为高斯消元法（Gauss Elimination）\n",
    "\n",
    "得到阶梯矩阵后，使用**矩阵回代法**可得矩阵的**行简化阶梯形式（row reduced echelon form, rref）**。这一步和上一步合在一起，称作行简化算法。\n",
    "\n",
    "将上述的行简化算法应用到方程组的增广场矩阵上，将直接得出方程组的解。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "rref (generic function with 1 method)"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 行简化算法，输出为矩阵的 行简化阶梯形式\n",
    "function rref(A::Matrix)\n",
    "    A = Float64.(A)  # 统一转换为 Float64\n",
    "    nr, nc = size(A)\n",
    "    i = j = 1\n",
    "    \n",
    "    while i <= nr && j <= nc\n",
    "        (m, mi) = findmax(abs.(A[i:end,j]))  # 选择一列中绝对值最大的元素作为主元（partial pivoting）\n",
    "        mi = mi+i - 1  # 计算得 主元m 在 矩阵A 中的列索引\n",
    "        \n",
    "        if m <= eps(Float64)  # 说明 A[i:,j] 全为 0\n",
    "            A[i:end, j] .= zero(Float64)\n",
    "            j += 1  # 该列已经是最简了，直接跳到下一列\n",
    "        else\n",
    "            A[i, :], A[mi, :] = A[mi, :], A[i, :]  # 通过行交换，将主元移到主元位置上\n",
    "            A[i, :] ./= A[i, j]  # 放缩主元所在行\n",
    "            \n",
    "            # 消除掉该列除主元外的所有元素\n",
    "            for k = 1:nr\n",
    "                if k != i\n",
    "                    A[k, :] .-= A[i, :] * A[k, j] / A[i, j]\n",
    "                end\n",
    "            end\n",
    "            \n",
    "            i += 1\n",
    "            j += 1\n",
    "        end\n",
    "    end\n",
    "    A  # 返回结果\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×6 Array{Float64,2}:\n",
       "  1.0   0.0  -2.0   3.0  0.0  -24.0\n",
       "  0.0   1.0  -2.0   2.0  0.0   -7.0\n",
       " -0.0  -0.0  -0.0  -0.0  1.0    4.0"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 有方程组 Ax = b\n",
    "A = [3 -9 12 -9 6\n",
    "     3 -7  8 -5 8\n",
    "     0  3 -6  6 4]\n",
    "\n",
    "b = [15\n",
    "      9\n",
    "     -5]\n",
    "\n",
    "rref([A b])  # 计算增广场矩阵的行简化阶梯形式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 三、解的存在性\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "线性方程组的解有三种可能：\n",
    "1. 无解\n",
    "2. 有唯一解\n",
    "3. 有无穷解（有自有变量）\n",
    "\n",
    "### 1. 无解\n",
    "\n",
    "无解，从线性方程组的角度来说，就是存在互相矛盾的方程，比如\n",
    "$$\\begin{cases}\n",
    "    x& + & y & = 0\\\\\n",
    "    x& + & y & = 3\n",
    "\\end{cases}$$\n",
    "\n",
    "从向量的线性组合的角度来说，就是 $向量b$ 不在 $A$ 的列向量所张成的向量空间之内。\n",
    "\n",
    "从矩阵方程的角度来说，就是增广矩阵的阶梯形式包含如下形式的行（b 不为 0）\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "    0 & ... & 0 & b\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "也就是说矩阵的增广列成了主元列，无解。\n",
    "\n",
    "### 2. 有唯一解\n",
    "\n",
    "方程组没有自由变量时，矩阵方程 $Ax=b$ 有唯一解。\n",
    "\n",
    "这表示增广矩阵除增广列外的每一列都得是主元列，或者说增广矩阵的主元列数等于方程组的未知数个数。（后面我们会看到，这也是矩阵A可逆的充要条件）\n",
    "\n",
    "### 3. 有无穷解\n",
    "\n",
    "方程组存在自由变量时，方程组有无穷解。这是因为自由变量可以取任意值。\n",
    "\n",
    "这时增广矩阵的主元列数少于方程组的未知数个数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.0.1",
   "language": "julia",
   "name": "julia-1.0"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.0.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
